﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinaryTree
{
    public class BTreeWithVisitor:ITree
    {
        public treeNode root;
        public BTreeWithVisitor()
        {
            root = null;
        }
        public BTreeWithVisitor(treeNode _root)
        {
            root = _root;
        }
        public  void TraverseLVR(treeNode _root, IVisit v)
        {
            if (_root != null)
            {
                TraverseLVR(_root.left, v);
                v.Visit(_root);
                TraverseLVR(_root.right, v);
            }
        }
        public void TraverseVLR(treeNode _root, IVisit v)
        {
            if (_root != null)
            {
                v.Visit(_root);
                TraverseVLR(_root.left, v);
                TraverseVLR(_root.right, v);
            }
        }
        public void TraverseLRV(treeNode _root, IVisit v)
        {
            if (_root != null)
            {                
                TraverseVLR(_root.left, v);
                TraverseVLR(_root.right, v);
                v.Visit(_root);
            }
        }
        public void AddNode(int val)
        {
            addNode(ref root, val);
        }
        private void addNode( ref treeNode _root, int val)
        {
            treeNode valroot = new treeNode(val);
            if (_root == null)
            {
                _root = valroot;
            }
            else
            {
                if (val < _root.value)
                {
                    addNode(ref _root.left, val);
                }
                else
                {
                    addNode(ref _root.right, val);
                }
            }
        }
        public int AmountOfLeaves()
        {
           IVisit v =new VAmountOfLeaves();
           TraverseVLR(root, v);
           return v.Amount;
        }
         public int AmountOfNodes()
        {
            IVisit v=new VAmountOfNodes();
            TraverseVLR(root, v);
            return v.Amount;
        }
        public int TotalAmountOfNodes()
        {
            return AmountOfNodes() + AmountOfLeaves();
        }
        private int AmountOfNodesOnILevel(treeNode _root, int i)
        {
            int amount = 0;
            if (i > 0)
            {
                if (_root == null)
                {
                    amount = 0;
                }
                else
                {
                    if (i == 1)
                    {
                        amount = 1;
                    }
                    else
                    {
                        amount = AmountOfNodesOnILevel(_root.left, i - 1) + AmountOfNodesOnILevel(_root.right, i - 1);
                    }
                }
            }
            return amount;
        }
        public int Width()
        {
            int w = 0;
            int[] width = new int[Height()];
            for (int i = 0; i < width.Length; i++)
            {
                width[i] = AmountOfNodesOnILevel(root, i + 1);
            }
            if (width.Length != 0)
            {
                w = width[0];
            }
            for (int i = 1; i < width.Length; i++)
            {
                if (w < width[i])
                {
                    w = width[i];
                }
            }
            return w;
        }
        public int Height()
        {
            IVisit v = new VHeight();
            v.Visit(root);
            return v.Amount;
        }
        public List<int> SortValuePrint()
        {
            IVisit v = new VInOrder();
            VInOrder.rez = new List<int>();
            TraverseLVR(root, v);
            //inorder(root, ref rez);
            return VInOrder.rez;
        }
        public void Revers()
        {
            Revers(ref root);
        }
        private void Revers(ref treeNode _root)
        {
            treeNode temp = null;
            if (_root != null)
            {
                temp = _root.right;
                _root.right = _root.left;
                _root.left = temp;
                Revers(ref _root.left);
                Revers(ref _root.right);
            }
        }
        public treeNode Search(int val)
        {
            return Search(ref root, val);
        }
        private treeNode Search(ref treeNode _root,int val)
        {
            treeNode node=null;
            if (_root != null)
            {
                if (_root.value == val)
                {
                    node = _root;
                }
                else
                {
                    if (val < _root.value)
                    {
                        node=Search(ref _root.left, val);
                    }
                    else
                    {
                        node=Search(ref _root.right, val);
                    }

                }
            }
            return node;
        }
        //public int Height()
        //{
        //    return Height(root);
        //}
        //private int Height(treeNode _root)
        //{
        //    int h = 0;
        //    if (_root != null)
        //    {
        //        h = Math.Max(Height(_root.right), Height(_root.left)) + 1;
        //    }
        //    return h;
        //}
        public void DelNode(int val)
        {
            treeNode node = Search(val);
            if (node != null)
            {
                setNull(ref root, val);
                if (node.left == null)
                {
                    addTree(ref node.right);
                }
                else
                {
                    if (node.right == null)
                    {
                        addTree(ref node.left);
                    }
                    else
                    {
                        addTree(ref node.left);
                        addTree(ref node.right);
                    }
                }
            }
        }
        private void addTree(ref treeNode _root)
        {
            if (_root != null)
            {
                addNode(ref root, _root.value);
                if (_root.left != null)
                {
                    addTree(ref _root.left);
                }
                if (_root.right != null)
                {
                    addTree(ref _root.right);
                }
            }
        }
        private void setNull(ref treeNode _root, int val)
        {
            if (_root != null)
            {
                if (_root.value == val)
                {
                    _root=null;
                }
                else
                {
                    if (val < _root.value)
                    {
                        setNull(ref _root.left, val);
                    }
                    else
                    {
                        setNull(ref _root.right, val);
                    }

                }
            }
        }
    }
}
